package MiddlePractice;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

import org.junit.Test;

public class Demo438 {
	
//	438. 找到字符串中所有字母异位词
//	给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。
//
//	异位词 指由相同字母重排列形成的字符串（包括相同的字符串）。

	int[] charNum = new int[26];
	
	public List<Integer> findAnagrams(String s, String p) {
		if(p.length() > s.length()) {
			return new LinkedList<>();
		}
		
		for(int i=0; i<p.length(); i++) {
			charNum[p.charAt(i) - 'a'] ++;
		}
		
		List<Integer> ans = new LinkedList<>();
		
		for(int i=0, j=i+p.length()-1; j<s.length(); i++, j++) {
			
			boolean res = isSame(s, i, j);
			if(res) {
				ans.add(i);
			}
		}
		return ans;
    }
	
	private boolean isSame(String s, int i, int j) {
		
		int[] nums = Arrays.copyOf(charNum, charNum.length);
		
		for(int r=i; r<=j; r++) {
			nums[s.charAt(r) - 'a']--;
		}
		
		for(int num : nums) {
			if(num != 0) {
				return false;
			}
		}
		
		return true;
	}

	@Test
	public void test_438() {
		findAnagrams("abab", "ab");
		
	}
}
